import heapq
from bisect import bisect_left, bisect_right
from collections import deque
from functools import reduce
from heapq import heappop, heappush
from itertools import combinations
from operator import xor

from .data_struct import *
from .method import *


def solution_2235(num1: int, num2: int) -> int:
    return num1 + num2


def solution_2487(head: Optional[ListNode]) -> Optional[ListNode]:
    # 双向链表
    if head is None or head.next is None:
        return head
    d_head = DListNode(head)
    p = head
    q = d_head
    while p.next is not None:
        q.next = DListNode(p.next)
        q.next.prev = q
        q = q.next
        p = p.next
    head = q.val
    q = q.prev
    while q is not None:
        if q.val.val >= head.val:
            temp = head
            head = q.val
            head.next = temp
        q = q.prev
    return head


def solution_2487_2(head: Optional[ListNode]) -> Optional[ListNode]:
    # 反转链表
    def reverse(head_re: ListNode) -> ListNode:
        dummy = ListNode(head_re.val)
        while head_re is not None:
            p_re = head_re
            head_re = head_re.next
            p_re.next = dummy.next
            dummy.next = p_re
        return dummy.next

    head = reverse(head)
    # 找左侧有更大数值的节点删除
    p = head
    while p is not None and p.next is not None:
        if p.next.val < p.val:
            p.next = p.next.next
        else:
            p = p.next
    return reverse(head)


def solution_2487_3(head: Optional[ListNode]) -> Optional[ListNode]:
    # 单调栈
    stack = []
    p = head
    rest = ListNode(-1)
    while p is not None:
        while not len(stack) == 0:
            if p.val > stack[len(stack) - 1].val:
                stack.pop()
            else:
                stack[len(stack) - 1].next = p
                stack.append(p)
                break
        if len(stack) == 0:
            stack.append(p)
            rest.next = p
        p = p.next
    return rest.next


def solution_2397(matrix: List[List[int]], numSelect: int) -> int:
    com_arrays = com_iteration(len(matrix[0]), numSelect)
    count_arrays = []
    for com_item in com_arrays:
        matrix_copy = []
        for i in range(len(matrix)):
            matrix_copy.append(list(matrix[i]))
        for i in range(len(matrix_copy)):
            for j in range(len(matrix_copy[0])):
                if j + 1 in com_item:
                    matrix_copy[i][j] = 0
        count = 0
        for row in matrix_copy:
            if sum(row) == 0:
                count += 1
        count_arrays.append(count)
    return max(count_arrays)


def solution_2397_2(matrix: List[List[int]], numSelect: int) -> int:
    # 预处理矩阵,压缩成m*1的数组,用二进制数表示
    m = len(matrix)
    n = len(matrix[0])
    mask = [0] * m
    for i in range(m):
        for j in range(n):
            mask[i] += matrix[i][j] << (n - j - 1)
    # 用一个整数来表述所有组合,不满足的跳过即可
    limit = 1 << n
    res = 0
    for i in range(limit):
        if pop_count(i) != numSelect:
            continue
        count = 0
        for j in range(m):
            if mask[j] & i == mask[j]:
                count += 1
        res = max(res, count)
    return res


def solution_2397_3(matrix: List[List[int]], numSelect: int) -> int:
    # 预处理矩阵,压缩成m*1的数组,用二进制数表示
    m = len(matrix)
    n = len(matrix[0])
    mask = [0] * m
    for i in range(m):
        for j in range(n):
            mask[i] += matrix[i][j] << (n - j - 1)
    # Gosper's Hack
    res = 0
    limit = 1 << n
    cur = (1 << numSelect) - 1
    while cur < limit:
        count = 0
        for j in range(m):
            if mask[j] & i == mask[j]:
                count += 1
        res = max(res, count)
        lb = cur & -cur  # 取最低位的1
        r = cur + lb  # 在cur最低位的1上加1
        cur = ((r ^ cur) >> count_trailing_zeros(lb) + 2) | r
    return res


def solution_2085(words1: List[str], words2: List[str]) -> int:
    f = {}
    for word in words1:
        if word not in f:
            f[word] = 1
        else:
            f[word] += 1
    for word in f:
        if f[word] > 1:
            f[word] = 3
    for word in words2:
        if word in f:
            f[word] += 1
    count = 0
    for word in f:
        if f[word] == 2:
            count += 1
    return count


def solution_2182(s: str, repeatLimit: int) -> str:
    nums_ch = [0] * 26
    ord_a = ord('a')
    for ch in s:
        nums_ch[ord(ch) - ord_a] += 1
    i = 25
    res = ''
    count = 0
    while i >= 0:
        if nums_ch[i] == 0:
            i -= 1
            continue
        else:
            res += chr(ord_a + i)
            nums_ch[i] -= 1
            count += 1
            if nums_ch[i] == 0:
                i -= 1
                count = 0
                continue
            if count == repeatLimit:
                j = i - 1
                while nums_ch[j] == 0:
                    j -= 1
                if j < 0:
                    return res
                res += chr(ord_a + j)
                nums_ch[j] -= 1
                count = 0
    return res


def solution_2182_2(s: str, repeatLimit: int) -> str:
    # 优先队列
    # 先存一下每个字符的次数
    pq = PriorityQueue()
    nums_ch = [0] * 26
    ord_a = ord('a')
    for ch in s:
        nums_ch[ord(ch) - ord_a] += 1
        if nums_ch[ord(ch) - ord_a] == 1:
            pq.put(ord(ch) - ord_a)  # 保证没有重复
    res = ''
    count = 0
    while not pq.empty():
        tmp = pq.delete()
        if tmp is None:
            return res
        res += chr(ord_a + tmp)
        count += 1
        nums_ch[tmp] -= 1
        if nums_ch[tmp] == 0:
            count = 0
            continue
        if count < repeatLimit:
            pq.put(tmp)
        else:
            sub_tmp = pq.delete()
            if sub_tmp is None:
                return res
            res += chr(ord_a + sub_tmp)
            count = 0
            nums_ch[sub_tmp] -= 1
            if nums_ch[sub_tmp] != 0:
                pq.put(sub_tmp)
            pq.put(tmp)
    return res


def solution_2376(n: int) -> int:
    s = str(n)
    # dp 需要的空间
    # M = s.length
    # n最大是个10位数
    # 二进制从低到高第 i 位为 1 表示 i 在集合中，为 0 表示 i 不在集合中。例如集合 {0,2,3} 对应的二进制数为 1101
    # 要求n各位互不相同，因此只需要9位就能表示所有的情况
    # 987654321 => 111111111 => (1<<10 -1)
    # dp = [[-1] * (1 << 10)] * len(s)# 重复指针，会出错
    dp = [[-1] * (1 << 10) for _ in range(len(s))]

    def dfs(i: int, mask: int, limit: bool, num: bool) -> int:
        # 末尾判断
        if i == len(s):
            return 1 if num else 0
        # 只有不受限制并且dp已经计算过的情况下，才能复用
        if not limit and num and dp[i][mask] != -1:
            return dp[i][mask]
        res = 0
        # 前导0，如果还没开始，比如n=999，现在检查9，那么就是009
        if not num:
            # 先考虑继续为0的情况
            # 如果高位取了0，一定比n小，limit必定False
            res += dfs(i + 1, mask, False, False)
        # 再考虑不是0的情况
        low = 0 if num else 1
        high = int(s[i]) if limit else 9  # 如果顶到上限了，那么这里检查的不能超过ｎ
        for x in range(low, high + 1):
            if ((mask >> x) & 1) == 0:
                res += dfs(i + 1, mask | (1 << x), limit and x == high, True)
        dp[i][mask] = res
        return res

    count = dfs(0, 0, True, False)
    return count


def solution_2376_2(n: int) -> int:
    return countSpecialNumbers(n)


def solution_2171(beans: List[int]) -> int:
    beans.sort()
    s = [beans[0]]
    n = len(beans)
    for i in range(1, n):
        s.append(beans[i] + s[i - 1])
    total = s[n - 1]
    min_beans = 10 ** 10
    for i in range(0, n):
        tmp = total - (n - i) * beans[i]
        if min_beans > tmp:
            min_beans = tmp
    return min_beans


def solution_2476(root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:
    # TL
    ans = []
    for q in queries:
        p = root
        left = -1
        right = -1
        while p is not None:
            if q < p.val:
                right = p.val
                p = p.left
            elif q > p.val:
                left = p.val
                p = p.right
            else:
                left = right = q
                break
        ans.append([left, right])
    return ans


def solution_2476_2(root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:
    a = []

    def dfs(node: Optional[TreeNode]) -> None:
        if node is None:
            return
        dfs(node.left)
        a.append(node.val)
        dfs(node.right)

    dfs(root)
    n = len(a)
    ans = []
    for q in queries:
        j = bisect_left(a, q)
        mx = a[j] if j < n else -1
        if j == n or a[j] != q:
            j -= 1
        mn = a[j] if j >= 0 else -1
        ans.append([mn, mx])
    return ans


def solution_2368(n: int, edges: List[List[int]], restricted: List[int]) -> int:
    g = [[] * n for _ in range(n)]
    for a, b in edges:
        g[a].append(b)
        g[b].append(a)

    ans = 0
    s_r = set(restricted)

    def dfs(node, p):
        nonlocal ans
        ans += 1
        for x in g[node]:
            if x not in s_r and x != p:
                dfs(x, node)

    dfs(0, -1)
    return ans


def solution_2369(nums: List[int]) -> bool:
    n = len(nums)

    @cache
    def dfs(left):
        if left >= n - 1:
            return False
        if left + 2 == n:
            if nums[left] == nums[left + 1]:
                return True
            else:
                return False
        if left + 3 == n:
            if nums[left] == nums[left + 1] == nums[-1]:
                return True
            elif nums[left] + 1 == nums[left + 1] and nums[left + 1] + 1 == nums[left + 2]:
                return True
            else:
                return False
        res = False
        if nums[left] == nums[left + 1]:
            res = res or dfs(left + 2)
        if nums[left] == nums[left + 1] == nums[left + 2]:
            res = res or dfs(left + 3)
        if nums[left] + 1 == nums[left + 1] and nums[left + 1] + 1 == nums[left + 2]:
            res = res or dfs(left + 3)
        return res

    return dfs(0)


def solution_2369_2(nums: List[int]) -> bool:
    n = len(nums)
    f = [True] + [False] * n
    # nums 的前 i 个数能否有效划分
    for i, x in enumerate(nums):
        if (i > 0 and f[i - 1] and x == nums[i - 1]) or (
                i > 1 and f[i - 2] and (
                (x == nums[i - 1] == nums[i - 2]) or (x == nums[i - 1] + 1 == nums[i - 2] + 2))):
            f[i + 1] = True
    return f[n]


def solution_2386(nums: List[int], k: int) -> int:
    ms = 0
    for i, x in enumerate(nums):
        if x >= 0:
            ms += x
        else:
            nums[i] = -x
    nums.sort()
    h = [(0, 0)]  # 空子序列
    # Dijkstra
    for _ in range(k - 1):
        s, i = heapq.heappop(h)
        if i < len(nums):
            # 在子序列的末尾添加nums[i]
            heapq.heappush(h, (s + nums[i], i + 1))  # 下一个添加/替换的元素下标为 i+1
            if i:  # 替换子序列的末尾元素为 nums[i]
                heapq.heappush(h, (s + nums[i] - nums[i - 1], i + 1))
    return ms - h[0][0]


def solution_2386_2(nums: List[int], k: int) -> int:
    """
    二分答案 + dp
    # 判断是否有至少k个子序列，其元素和s不超过sum_limit
    """
    s = 0
    for i, x in enumerate(nums):
        if x >= 0:
            s += x
        else:
            nums[i] = -x
    nums.sort()

    def check(sum_limit: int) -> bool:
        cnt = 1  # 空序列

        def dfs(i: int, s: int) -> None:
            nonlocal cnt
            if cnt == k or i == len(nums) or s + nums[i] > sum_limit:
                return
            cnt += 1  # 选了i 子序列+1
            dfs(i + 1, s + nums[i])
            dfs(i + 1, s)

        dfs(0, 0)
        return cnt == k

    # 0到sum(nums)-1
    # 二分
    return s - bisect_left(range(sum(nums)), True, key=check)


def solution_2129(title: str) -> str:
    words = title.split(" ")
    n = len(words)
    for i in range(n):
        words[i] = words[i].lower()
        if len(words[i]) > 2:
            words[i] = chr(ord(words[i][0]) - 32) + words[i][1:]
    return ' '.join(words)


def solution_2129_2(title: str) -> str:
    title = list(title)
    n = len(title)
    blank_p = -1
    for i in range(n):
        if title[i] == ' ':
            if i - blank_p <= 3:
                title[blank_p + 1] = chr(ord(title[blank_p + 1]) + 32)
            blank_p = i
            continue
        else:
            if i - 1 == blank_p:
                if (cur := ord(title[i])) >= 97:
                    title[i] = chr(cur - 32)
            else:
                if (cur := ord(title[i])) < 97:
                    title[i] = chr(cur + 32)
    if n - blank_p <= 3:
        title[blank_p + 1] = chr(ord(title[blank_p + 1]) + 32)
    return ''.join(title)


def solution_2312(m: int, n: int, prices: List[List[int]]) -> int:
    # 定义f[i][j] 表示切割一块高i宽j的木块, 能得到的最多钱数
    # 1. 直接卖
    # 2. 竖着切开,枚举切割位置k, f[i][j] = max f[i][k]+f[i][j-k]
    # 3. 横着切开,枚举切割位置k, f[i][j] = max f[k][j]+f[i-k][j]
    # 取三种情况的最大值
    # ans = f[m][n]
    pr = {(h, w): p for h, w, p in prices}
    f = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            f[i][j] = max(pr.get((i, j), 0), max(((f[i][k] + f[i][j - k]) for k in range(1, j)), default=0),
                          max(((f[k][j] + f[i - k][j]) for k in range(1, i)), default=0))
    return f[m][n]


def solution_2312_2(m: int, n: int, prices: List[List[int]]) -> int:
    f = [[0] * (n + 1) for _ in range(m + 1)]
    # 优化1 价格直接存入f中
    for h, w, p in prices:
        f[h][w] = p
    # 优化2 只需要遍历一半
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            f[i][j] = max(f[i][j], max(((f[i][k] + f[i][j - k]) for k in range(1, j // 2 + 1)), default=0),
                          max(((f[k][j] + f[i - k][j]) for k in range(1, i // 2 + 1)), default=0))
    return f[m][n]


def solution_2192(n: int, edges: List[List[int]]) -> List[List[int]]:
    ans = [set() for _ in range(n)]
    children = [set() for _ in range(n)]
    for u, v in edges:
        ans[v].add(u)
        children[u].add(v)
        children[u] = children[u].union(children[v])
        for parent in ans[u]:
            children[parent] = children[parent].union(children[u])
        ans[v] = ans[v].union(ans[u])
        for child in children[v]:
            ans[child] = ans[child].union(ans[v])
    ans = [sorted(list(x)) for x in ans]
    return ans


def solution_2192_2(n: int, edges: List[List[int]]) -> List[List[int]]:
    g = [[] for _ in range(n)]
    for x, y in edges:
        g[y].append(x)  # 反向建图

    def dfs(x: int) -> None:
        vis[x] = True
        for y in g[x]:
            if not vis[y]:
                dfs(y)  # 不走重复

    ans = [None] * n
    for i in range(n):
        vis = [False] * n
        dfs(i)
        vis[i] = False
        ans[i] = [j for j, b in enumerate(vis) if b]
    return ans


def solution_2009(nums: List[int]) -> int:
    """
    1. 正难则反
    2. nums去重
    3. 滑动窗口，枚举右端点，题目的要求使得窗口在数轴上的长度恒定，从而可以确定左端点
    """
    nums.sort()
    n = len(nums)
    a = sorted(set(nums))
    ans = left = 0
    for i, x in enumerate(a):
        while a[left] < x - n + 1:
            left += 1
        ans = max(ans, i - left + 1)
    return n - ans


def solution_2007(changed: List[int]) -> List[int]:
    cnt = Counter(changed)
    cnt0 = cnt[0]
    ans = []
    if cnt0 % 2 != 0:
        return ans
    ans += [0] * (cnt0 // 2)
    cnt.pop(0, 0)
    for key in cnt:
        x = key
        if x % 2 == 0 and x / 2 in cnt:
            continue
        while x in cnt:
            cnt_x = cnt[x]
            if cnt_x > cnt[x * 2]:
                return []
            ans += [x] * cnt_x
            if cnt_x < cnt[x * 2]:
                cnt[x * 2] -= cnt_x
                x *= 2
            else:
                x *= 4
    return ans


def solution_2385(root: Optional[TreeNode], start: int) -> int:
    # 不一定是根节点拐弯
    # res = [0, False]
    # t3 = 0
    #
    # def dfs(node: TreeNode, left: bool, depth: int) -> int:
    #     nonlocal t3
    #     if not node:
    #         return 0
    #     t1 = dfs(node.left, left, depth + 1)
    #     t2 = dfs(node.right, left, depth + 1)
    #     if node.val == start:
    #         res[0], res[1] = depth, left
    #         t3 = max(t1, t2)
    #     return max(t1, t2) + 1
    #
    # t4 = dfs(root.right, False, 1)
    # t5 = dfs(root.left, True, 1)
    # if res[0] == 0:
    #     return max(t4, t5)
    # else:
    #     if not res[1]:
    #         t = max(t3, res[0] + t5)
    #     else:
    #         t = max(t3, res[0] + t4)
    #     return t
    """
    1. 返回值返回子树最大链长度，和start是否在子树中
    2. 如果当前节点是空节点，返回0和false
    3. 左子树返回l_len，右子树返回r_len
    4. 当前节点值等于start，初始化答案为max(l_len, r_len)，返回1,true
    5. 左右子树都不含start，返回max(l_len, r_len)+1
    6. 左右子树其中一个包含start，用l_len+r_len更新答案
    """

    ans = 0

    def dfs(node: Optional[TreeNode]) -> (int, bool):
        if node is None:
            return 0, False
        l_len, l_found = dfs(node.left)
        r_len, r_found = dfs(node.right)
        nonlocal ans
        if node.val == start:
            ans = max(l_len, r_len)
            return 1, True
        if l_found or r_found:
            ans = max(ans, l_len + r_len)
            return (l_len if l_found else r_len) + 1, True
        return max(l_len, r_len) + 1, False

    dfs(root)
    return ans


def solution_2462(costs: List[int], k: int, candidates: int) -> int:
    n = len(costs)
    left, right = 0, n - 1
    h = []
    if candidates * 2 >= n:
        h = costs
        heapq.heapify(h)
        cnt = 0
        ans = 0
        while cnt < k:
            tmp = heapq.heappop(h)
            ans += tmp
            cnt += 1
        return ans
    while left < candidates:
        heapq.heappush(h, (costs[left], -1))
        left += 1
    while n - 1 - right < candidates:
        heapq.heappush(h, (costs[right], 1))
        right -= 1
    cnt = 0
    ans = 0
    while left <= right and cnt < k:
        tmp = heapq.heappop(h)
        ans += tmp[0]
        if tmp[1] == -1:
            heapq.heappush(h, (costs[left], -1))
            left += 1
        else:
            heapq.heappush(h, (costs[right], 1))
            right -= 1
        cnt += 1
    while cnt < k:
        tmp = heapq.heappop(h)
        ans += tmp[0]
        cnt += 1
    return ans


def solution_2079(plants: List[int], capacity: int) -> int:
    i = 0
    cur = -1
    cur_water = capacity
    ans = 0
    while i < len(plants):
        ans += i - cur
        cur = i
        if i == len(plants) - 1:
            return ans
        cur_water -= plants[i]
        if cur_water < plants[i + 1]:
            cur = -1
            ans += i - cur
            cur_water = capacity
        i += 1
    return ans


def solution_2105(plants: List[int], capacityA: int, capacityB: int) -> int:
    n = len(plants)
    left, right = 0, n - 1
    cap_l, cap_r = capacityA, capacityB
    ans = 0
    while left < right:
        if plants[left] > cap_l:
            ans += 1
            cap_l = capacityA
        if plants[right] > cap_r:
            ans += 1
            cap_r = capacityB
        cap_l -= plants[left]
        cap_r -= plants[right]
        left += 1
        right -= 1

    return ans + (1 if left == right and (plants[left] > max(cap_l, cap_r)) else 0)


def solution_2391(garbage: List[str], travel: List[int]) -> int:
    ans = 0
    last_m, last_p, last_g = 0, 0, 0
    for i, g in enumerate(garbage):
        for c in g:
            if c == 'M':
                last_m = i
            elif c == 'P':
                last_p = i
            elif c == 'G':
                last_g = i
            ans += 1
    ans += sum(travel[:last_m]) + sum(travel[:last_p]) + sum(travel[:last_g])
    return ans


def solution_2244(tasks: List[int]) -> int:
    cnt = Counter(tasks)
    ans = 0
    f = {1: -1, 2: 1, 3: 1, 4: 2, 5: 2, 6: 2, 7: 3}
    for v in cnt.values():
        if v == 1:
            return -1
        if v >= 5:
            t = v - 5
            ans += t // 3
            t = t % 3 + 5
            ans += f[t]
        else:
            ans += f[v]
    return ans


def solution_2225(matches: List[List[int]]) -> List[List[int]]:
    ans = [[], []]
    cnt = {}
    for match in matches:
        if match[0] not in cnt:
            cnt[match[0]] = 0
        if match[1] not in cnt:
            cnt[match[1]] = 1
        else:
            cnt[match[1]] += 1
    for c in cnt:
        if cnt[c] == 0:
            ans[0].append(c)
        elif cnt[c] == 1:
            ans[1].append(c)
    return [sorted(ans[0]), sorted(ans[1])]


def solution_2028(rolls: List[int], mean: int, n: int) -> List[int]:
    m = len(rolls)
    total = (m + n) * mean
    t1 = sum(rolls)
    t2 = total - t1
    if not n <= t2 <= n * 6:
        return []
    base = t2 // n
    res = t2 - n * base
    # if base > 6 or (base == 6 and res > 0) or base <= 0:
    #     return []
    ans = [base] * n
    i = 0
    while res > 0:
        ans[i] = min(6, res + base)
        res -= ans[i] - base
        i += 1
    return ans


def solution_2255(words: List[str], s: str) -> int:
    def prefix(w):
        if len(w) > len(s):
            return False
        for i in range(len(w)):
            if w[i] != s[i]:
                return False
        return True

    ans = 0
    for w in words:
        if prefix(w):
            ans += 1
    return ans


def solution_2288(sentence: str, discount: int) -> str:
    words = sentence.split(" ")
    for i in range(len(words)):
        w = words[i]
        if len(w) <= 1 or w[0] != "$":
            continue
        for c in w[1:]:
            if not c.isdigit():
                break
        else:
            x = int(w[1:]) * (100 - discount) * 0.01
            words[i] = '$' + format(x, ".2f")
    return " ".join(words)


def solution_2220(start: int, goal: int) -> int:
    t = start ^ goal
    ans = 0
    while t > 0:
        ans += 1
        t &= t - 1
    return ans


def solution_2419(nums: List[int]) -> int:
    ans = mx = cnt = 0
    for x in nums:
        if x > mx:
            mx = x
            ans = cnt = 1
        elif x == mx:
            cnt += 1
            if cnt > ans:
                ans = cnt
        else:
            cnt = 0
    return ans


def solution_2401(nums: List[int]) -> int:
    left = ans = 0
    s = 0
    for right, x in enumerate(nums):
        while x & s != 0:
            t = nums[left]
            s = s & ~t
            left += 1
        s = s | x
        ans = max(ans, right - left + 1)
    return ans


def solution_2429(num1: int, num2: int) -> int:
    cnt = 0
    while num2 > 0:
        num2 &= num2 - 1
        cnt += 1
    ans = 0
    for i in range(31, -1, -1):
        if cnt == i + 1:
            ans |= (1 << cnt) - 1
            cnt = 0
        elif (num1 >> i) & 1:
            cnt -= 1
            ans |= 1 << i
        if cnt == 0:
            return ans
    return -1


def solution_2065(values: List[int], edges: List[List[int]], maxTime: int) -> int:
    n = len(values)
    g = [[] for _ in range(n)]
    for x, y, t in edges:
        g[x].append((y, t))
        g[y].append((x, t))

    # Dijkstra 算法
    dis = [inf] * n
    dis[0] = 0
    h = [(0, 0)]
    while h:
        dx, x = heappop(h)
        if dx > dis[x]:  # x 之前出堆过
            continue
        for y, d in g[x]:
            new_dis = dx + d
            if new_dis < dis[y]:
                dis[y] = new_dis  # 更新 x 的邻居的最短路
                heappush(h, (new_dis, y))
    ans = 0
    vis = [False] * n
    vis[0] = True

    def dfs(x: int, sum_time: int, sum_value: int) -> None:
        if x == 0:
            nonlocal ans
            ans = max(ans, sum_value)
        for y, t in g[x]:
            if sum_time + t + dis[y] > maxTime:
                continue
            if vis[y]:
                dfs(y, sum_time + t, sum_value)
            else:
                vis[y] = True
                dfs(y, sum_time + t, sum_value + values[y])
                vis[y] = False

    dfs(0, 0, values[0])
    return ans


def solution_2411(nums: List[int]) -> List[int]:
    n = len(nums)
    ans = [0] * n
    for i, x in enumerate(nums):
        ans[i] = 1
        for j in range(i - 1, -1, -1):
            if (nums[j] | x) == nums[j]:
                break
            nums[j] |= x
            ans[j] = i - j + 1
    return ans


def solution_2154(nums: List[int], original: int) -> int:
    mask = 0
    for x in nums:
        t = x // original
        res = x % original
        if res == 0 and t & (t - 1) == 0:
            mask |= t & -t
    mask = ~ mask
    return (mask & -mask) * original


def solution_2354(nums: List[int], k: int) -> int:
    cnt = Counter(x.bit_count() for x in set(nums))
    ans = 0
    for x1, v1 in cnt.items():
        for x2, v2 in cnt.items():
            if x1 + x2 >= k:
                ans += v1 * v2
    return ans


def solution_2101(bombs: List[List[int]]) -> int:
    n = len(bombs)
    g = [[] for _ in range(n)]
    for i, (x1, y1, r) in enumerate(bombs):
        for j, (x2, y2, _) in enumerate(bombs):
            if i != j and (x1 - x2) ** 2 + (y1 - y2) ** 2 <= r ** 2:
                g[i].append(j)

    def dfs(x, fa):
        seen.add(x)
        cnt = 1
        for y in g[x]:
            if y != fa and y not in seen:
                cnt += dfs(y, x)
        return cnt

    ans = 0
    for i in range(n):
        seen = set()
        ans = max(ans, dfs(i, -1))
    return ans


def solution_2275(candidates: List[int]) -> int:
    mx = max(candidates).bit_length()
    cnt = [0] * mx
    for x in candidates:
        for i in range(mx):
            if (x >> i) & 1:
                cnt[i] += 1
    return max(cnt)


def solution_2425(nums1: List[int], nums2: List[int]) -> int:
    ans = 0
    if len(nums2) % 2:
        ans ^= reduce(xor, nums1)
    if len(nums1) % 2:
        ans ^= reduce(xor, nums2)
    return ans


def solution_2024(answerKey: str, k: int) -> int:
    ans = left = 0
    cnt = defaultdict(int)
    for right, ch in enumerate(answerKey):
        cnt[ch] += 1
        while cnt['T'] > k and cnt['F'] > k:
            cnt[answerKey[left]] -= 1
            left += 1
        ans = max(ans, right - left + 1)
    return ans


def solution_2181(head: Optional[ListNode]) -> Optional[ListNode]:
    dummyhead = ListNode(-1, head)
    p = dummyhead
    while p:
        t = p.next
        if not t:
            break
        elif t.val != 0:
            cur = t.val
            q = t.next
            while q and q.val != 0:
                cur += q.val
                q = q.next
            t.val = cur
            t.next = q
            p = p.next
        else:
            p.next = t.next
    return dummyhead.next


def solution_2398(chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
    ans = s = left = 0
    q = deque()
    for right, (t, c) in enumerate(zip(chargeTimes, runningCosts)):
        # 单调队列
        while q and t >= chargeTimes[q[-1]]:
            q.pop()
        q.append(right)
        s += c

        while q and chargeTimes[q[0]] + (right - left + 1) * s > budget:
            if q[0] == left:  # q[0] 不一定会被移除，因此q[0] 可能在left右侧
                q.popleft()
            s -= runningCosts[left]
            left += 1

        ans = max(ans, right - left + 1)
    return ans


def solution_2390(s: str) -> str:
    ls = []
    for x in s:
        if x == '*':
            ls.pop()
        else:
            ls.append(x)
    return ''.join(ls)


def solution_2332(buses: List[int], passengers: List[int], capacity: int) -> int:
    buses.sort()
    passengers.sort()
    j = 0
    for t in buses:
        c = capacity
        while c and j < len(passengers) and passengers[j] <= t:
            j += 1
            c -= 1
    j -= 1  # 上面操作j存在额外+1
    ans = buses[-1] if c else passengers[j]  # 最后一辆有空 或者 最后一个上车的乘客
    while j >= 0 and ans == passengers[j]:  # 有人
        ans -= 1
        j -= 1
    return ans


def solution_2414(s: str) -> int:
    left = 0
    last = ord(s[left])
    ans = 1
    for right in range(1, len(s)):
        cur = ord(s[right])
        if cur != last + 1:
            ans = max(ans, right - left)
            left = right
        last = cur
    return max(ans, len(s) - left)


def solution_2374(edges: List[int]) -> int:
    n = len(edges)
    ans = [0] * n
    for i, x in enumerate(edges):
        ans[x] += i
    mx = -inf
    idx = -1
    for i, x in enumerate(ans):
        if mx < x:
            mx = x
            idx = i
    return idx


def maximumSubsequenceCount(self, text: str, pattern: str) -> int:
    cnt1 = 0
    cnt2 = 0
    ans = 0
    for x in text:
        if x == pattern[1]:
            cnt2 += 1
    if pattern[0] == pattern[1]:
        for x in range(1, cnt2 + 1):
            ans += x
        return ans
    mx = cnt2
    for x in text:
        if x == pattern[0]:
            cnt1 += 1
            ans += cnt2
        elif x == pattern[1]:
            cnt2 -= 1
    mx = max(cnt1, mx)
    ans += mx
    return ans


def solution_2306(ideas: List[str]) -> int:
    s = set()
    trie = Trie()
    for idea in ideas:
        s.add(idea[0])
        trie.insert(idea)
    f = Counter()
    for idea in ideas:
        a = idea[0]
        for b in s:
            if a == b:
                continue
            if not trie.search(b + idea[1:]):
                f[(a, b)] += 1
    ans = 0
    for a in s:
        for b in s:
            if a == b:
                continue
            ans += f[(a, b)] * f[(b, a)]
    return ans


def solution_2306_2(ideas: List[str]) -> int:
    size = [0] * 26
    intersection = [[0] * 26 for _ in range(26)]
    groups = defaultdict(set)
    for s in ideas:
        b = ord(s[0]) - ord('a')
        size[b] += 1
        g = groups[s[1:]]
        for a in g:
            intersection[b][a] += 1
            intersection[a][b] += 1
        g.add(b)

    ans = 0
    for a in range(1, 26):
        for b in range(a):
            m = intersection[a][b]
            ans += (size[a] - m) * (size[b] - m)
    return ans * 2


def solution_2496(strs: List[str]) -> int:
    ans = 0
    for s in strs:
        cur = 0
        for x in s:
            if x.isdigit():
                cur = cur * 10 + int(x)
            else:
                cur = len(s)
                break
        ans = max(ans, cur)
    return ans


def solution_2073(tickets: List[int], k: int) -> int:
    t = tickets[k]
    ans = 0
    for i, x in enumerate(tickets):
        if i <= k:
            ans += min(x, t)
        else:
            ans += min(x, t - 1)
    return ans


def solution_2187(time: List[int], totalTrips: int) -> int:
    def check(x):
        res = 0
        for t in time:
            res += x // t
        return totalTrips <= res

    min_t = min(time)
    avg = (totalTrips - 1) // len(time) + 1
    lo = min_t * avg - 1  # 循环不变量：sum >= totalTrips 恒为 False
    hi = min(max(time) * avg, min_t * totalTrips)  # 循环不变量：sum >= totalTrips 恒为 True
    return bisect_left(range(lo, hi + 1), True, key=check) + lo


def solution_2435(grid: List[List[int]], k: int) -> int:
    MOD = 10 ** 9 + 7

    m = len(grid)
    n = len(grid[0])

    @cache
    def dfs(i, j, res):
        if i == m - 1 and j == n - 1:
            return 1 if (res + grid[i][j]) % k == 0 else 0
        if i == m - 1:
            return dfs(i, j + 1, (res + grid[i][j]) % k)
        if j == n - 1:
            return dfs(i + 1, j, (res + grid[i][j]) % k)
        a = dfs(i, j + 1, (res + grid[i][j]) % k)
        b = dfs(i + 1, j, (res + grid[i][j]) % k)
        return (a + b) % MOD

    ans = dfs(0, 0, 0)
    dfs.cache_clear()
    return ans

def solution_2435_2(grid: List[List[int]], k: int) -> int:
    m = len(grid)
    n = len(grid[0])
    # dp[i][j][v] 走到i，j 路径和为v
    dp = [[[0] * (k) for _ in range(n + 1)] for _ in range(m + 1)]
    dp[0][1][0] = 1  # 不存在的地方有个起始处dp[0][1][0] 或dp[1][0][0]
    for i in range(m):
        for j in range(n):
            for v in range(k):
                dp[i + 1][j + 1][(v + grid[i][j]) % k] = (dp[i + 1][j][v] + dp[i][j + 1][v]) % MOD
    return dp[m][n][0]
